package day_2022_9_to_12.Day;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author haomin
 * @date 2022/11/15 21:11
 **/
public class Day71_Review {
    class Solution {
        public boolean exist(char[][] board, String word) {
            int m = board.length, n = board[0].length;
            for(int i = 0; i < m; ++i) {
                for(int j = 0; j < n; ++j) {
                    if(board[i][j] == word.charAt(0)) {
                        if(dfs(board, m, n, i, j, word, 0))
                            return true;
                    }
                }
            }
            return false;
        }
        private boolean dfs(char[][] board, int m, int n, int i, int j, String word, int k) {
            if(k == word.length()) return true;
            if(i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word.charAt(k)) return false;
            board[i][j] += 59;
            boolean result = dfs(board, m, n, i + 1, j, word, k + 1) ||
                    dfs(board, m, n, i - 1, j, word, k + 1) ||
                    dfs(board, m, n, i, j + 1, word, k + 1) ||
                    dfs(board, m, n, i, j - 1, word, k + 1);
            board[i][j] -= 59;
            return result;
        }
    }

    class Solution2 {
        public int cuttingRope(int n) {
            if(n < 4) return n == 1 ? 1 : n-1;
            int ans = 1;
            while(n > 4) {
                ans *= 3;
                n -= 3;
            }
            return ans * n;
        }
    }

    class Solution3 {
        int mod = (int)1e9 + 7;
        public int cuttingRope(int n) {
            if(n < 4) return n == 1 ? 1 : n-1;
            long ans = 1;
            while(n > 4) {
                ans = (ans * 3) % mod;
                n -= 3;
            }
            return (int)((ans * n) % mod);
        }
    }

    public class Solution4 {
        // you need to treat n as an unsigned value
        public int hammingWeight(int n) {
            int post = 32;
            int ans = 0;
            while(post-- > 0) {
                if((n & 1) == 1) ans++;
                n >>= 1;
            }
            return ans;
        }
    }

    class Solution5 {
        public double myPow(double x, int n) {
            double ans = 1.0;
            for(int i = n; i != 0; i /= 2){
                if(i % 2 != 0) ans *= x;
                x *= x;
            }
            return n < 0 ? 1/ans : ans;
        }
    }

    class Solution6 {
        public int[] printNumbers(int n) {
            int len = (int)Math.pow(10, n)-1;
            int[] ans = new int[len];
            for(int i = 0; i < len; ++i) ans[i] = i + 1;
            return ans;
        }
    }

    class Solution7 {
        public ListNode deleteNode(ListNode head, int val) {
            if(head == null) return head;
            ListNode dummyHead = new ListNode(-1);
            dummyHead.next = head;
            ListNode cur = dummyHead;
            while(cur.next.val != val) cur = cur.next;
            cur.next = cur.next.next;
            return dummyHead.next;
        }
    }

    class Solution7_2 {
        public ListNode deleteNode(ListNode head, int val) {
            if(head.val == val) return head.next;
            head.next = deleteNode(head.next, val);
            return head;
        }
    }

    class Solution8 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == p || root == q) return root;
            if(root.val < p.val && root.val < q.val) {
                return lowestCommonAncestor(root.right, p, q);
            }else if(root.val > p.val && root.val > q.val) {
                return lowestCommonAncestor(root.left, p, q);
            }else return root;
        }
    }

    class Solution9 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null) return null;
            if(root == p || root == q) return root;
            TreeNode l = lowestCommonAncestor(root.left, p, q);
            TreeNode r = lowestCommonAncestor(root.right, p, q);
            if(l != null && r != null) return root;
            if(l != null) return l;
            if(r != null) return r;
            return null;
        }
    }

    class Solution10 {
        public int[] exchange(int[] nums) {
            int l = 0, r = nums.length - 1;
            while(l < r) {
                while(l < r && nums[l] % 2 != 0) l++;
                while(l < r && nums[r] % 2 == 0) r--;
                if(l < r) {
                    int temp = nums[l];
                    nums[l] = nums[r];
                    nums[r] = temp;
                }
            }
            return nums;
        }
    }

    class Solution11 {
        public ListNode getKthFromEnd(ListNode head, int k) {
            Deque<ListNode> s = new LinkedList<>();
            while(head != null) {
                s.push(head);
                head = head.next;
            }
            while(k-- > 1) s.pop();
            return s.pop();
        }
    }

    class Solution11_2 {
        public ListNode getKthFromEnd(ListNode head, int k) {
            ListNode l1 = head;
            ListNode l2 = head;
            while(k-- > 0) l1 = l1.next;
            while(l1 != null) {
                l1 = l1.next;
                l2 = l2.next;
            }
            return l2;
        }
    }

    class Solution12 {
        public ListNode reverseList(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode second = head.next;
            ListNode newNode = reverseList(head.next);

            second.next = head;
            head.next = null;
            return newNode;
        }
    }

    class Solution12_2 {
        public ListNode reverseList(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode dummyHead = new ListNode(-1);
            while(head != null) {
                ListNode next = head.next;
                head.next = dummyHead.next;
                dummyHead.next = head;
                head = next;
            }
            return dummyHead.next;
        }
    }

    class Solution12_3 {
        public ListNode reverseList(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode pre = null;
            ListNode cur = head;
            while(cur != null) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            return pre;
        }
    }

    class Solution13 {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if(l1 == null) return l2;
            if(l2 == null) return l1;
            if(l1.val < l2.val){
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            }else {
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
        }
    }

    class Solution13_2 {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if(l1 == null) return l2;
            if(l2 == null) return l1;
            ListNode dummyHead = new ListNode(-1);
            ListNode cur = dummyHead;
            while(l1 != null && l2 != null) {
                if(l1.val < l2.val) {
                    cur.next = new ListNode(l1.val);
                    l1 = l1.next;
                    cur = cur.next;
                }else {
                    cur.next = new ListNode(l2.val);
                    l2 = l2.next;
                    cur = cur.next;
                }
            }
            if(l1 == null) cur.next = l2;
            if(l2 == null) cur.next = l1;
            return dummyHead.next;
        }
    }

    class Solution14 {
        public boolean isSubStructure(TreeNode A, TreeNode B) {
            if(A == null || B == null) return false;
            return isSub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
        }
        private boolean isSub(TreeNode a, TreeNode b) {
            if(b == null) return true;
            if(a == null ) return false;
            return a.val == b.val && isSub(a.left, b.left) && isSub(a.right, b.right);
        }
    }

    class Solution15 {
        public TreeNode mirrorTree(TreeNode root) {
            if(root == null) return null;
            TreeNode l = root.left;
            TreeNode r = root.right;
            root.left = r;
            root.right = l;
            mirrorTree(root.left);
            mirrorTree(root.right);
            return root;
        }
    }

    class Solution16 {
        public boolean isSymmetric(TreeNode root) {
            if(root == null) return true;
            return isSymmetricHelper(root.left, root.right);
        }
        private boolean isSymmetricHelper(TreeNode l, TreeNode r) {
            if(l == null && r == null) return true;
            if(l == null || r == null) return false;
            return l.val == r.val && isSymmetricHelper(l.left, r.right) && isSymmetricHelper(l.right, r.left);
        }
    }

    class MinStack {
        Deque<Integer> s1;
        Deque<Integer> s2;

        /** initialize your data structure here. */
        public MinStack() {
            s1 = new LinkedList<>();
            s2 = new LinkedList<>();
        }

        public void push(int x) {
            s1.push(x);
            if(s2.isEmpty()) s2.push(x);
            else {
                s2.push(s2.peek() < x ? s2.peek() : x);
            }
        }

        public void pop() {
            s1.pop();
            s2.pop();
        }

        public int top() {
            return s1.peek();
        }

        public int min() {
            return s2.peek();
        }
    }
}